package offer.easy.math;

public class NumOfOne {

    //设一个数为num，则它是一个x位数
    //当我们取到num的第i位时，将其分为三部分
    //当前取得位数为操作位，前面的位数为高位，后面的位数为低位，并增加位数因子
    //则当前位数的数字1个数，由操作位进行判断，高位和低位进行计数
    //数num中，数字1出现的个数，由操作位从个位到最高位进行累加求和
    //由于Java数操作中，先取低位，依次除十取高位是更适合程序循环的操作，因此操作位从个位开始累加
    /**
     * 例如：num数 2 1 0 6
     * 则设，操作位的数值为 cur，高位的数值为 high，低位的数值为 low，位数因子为 digit
     * cur = 6，low = 0，high = 210，位数因子 = 1
     * 操作位的判断分三个分支：cur=0，cur=1或cur=[2,3,4,5,6,7,8,9]
     * 当操作位为0时，由于低位已经累加过了，所以数字1的个数由高位决定
     * 当操作位为1时，由于操作位的1低位无法计算自身的个数，所以数字1的个数由高位与低位一同决定
     * 当操作位为2~9时，由于低位的累加已经可以记下当前位数所有的1，因此高位进1，所以数字1的个数由高位决定
     * 1@，cur=6，当前位数存在1的机会为210个，而本身位有一个1，累加就是211个，例如：0001,0011,0111,1111，只计算当前位数的1
     * 2@，cur=0，当前位数存在1的机会为21个，得积为21*10为210
     * 3@，cur=1，当前位数存在1的机会为2个，由于低位为6，则有2*100+6+1
     */

    /**
    case 1: cur=0
            2  3   0  4
    千位和百位可以选00 01 02....22  十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 中排列
    当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
    但是2301不应该算进来，这个1是 单独  出现在个位的（而11，121,111这种可以被算多次）
    即 23*10
            case 2: cur=1
            2  3  1  4
    千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
    当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
    即 23 *10 + 4 +1
            case 3: cur>1 即2-9
            2  3  2  4
    千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
    当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，分别是从个位和十位分析得到的1次）
    即 23 *10 + 10
     */

    public static int number(int n) {
        int cur = n%10;
        int high = n/10;
        int digit = 1;
        int low = 0;
        int sum = 0;

        while(high>0 || cur>0) {
            if (cur == 0) {
                sum = sum + high*digit;
            } else if (cur == 1) {
                sum = sum + high*digit + low + 1;
            } else {
                sum = sum + (high+1)*digit;
            }
            low = low + digit*cur;
            cur = high%10;
            high = high/10;
            digit = digit*10;
        }
        return sum;
    }

    public static int numberII(int n) {
        int sum = 0;
        int temp = 0;
        for (int i = 1; i <= n; i++) {
            temp = i;
            while (temp != 0) {
                if (temp%10 == 1) {
                    sum++;
                }
                temp = temp/10;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(number(10000));
        System.out.println(numberII(10000));
    }
}
